// https://leetcode.cn/problems/subarray-sum-equals-k/description/

// 算法思路总结：
// 1. 使用前缀和与哈希表统计和为k的子数组数量
// 2. 计算累计和并记录每个和出现的频率
// 3. 查找目标值sum-k是否存在哈希表中
// 4. 累加满足条件的子数组个数
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <unordered_map>

class Solution 
{
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        int m = nums.size();

        unordered_map<int, int> up;
        up[0] = 1;

        int ret = 0, sum = 0;
        for (int i = 0 ; i < m ; i++)
        {
            sum += nums[i];
            int target = sum - k;

            if (up.count(target) > 0)
            {
                ret += up[target];
            }
            
            up[sum]++;
        }

        return ret;
    }
};

int main()
{
    vector<int> nums1 = {1,1,1}, nums2 = {1,2,3};
    int k1 = 2, k2 = 3;

    Solution sol;

    cout << sol.subarraySum(nums1, k1) << endl;
    cout << sol.subarraySum(nums2, k2) << endl;

    return 0;
}